package com.sunkq.algorithms;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class ListNodeTest1 {

    @Test
    public void testReverseBetween(){
        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(2);
        listNode1.next.next = new ListNode(3);
        listNode1.next.next.next = new ListNode(4);
        listNode1.next.next.next.next = new ListNode(5);
        listNode1.next.next.next.next.next = new ListNode(6);
        ListNode listNode = reverseBetween(listNode1,2,4);
        while (listNode!=null){
            System.out.println(listNode.val);
            listNode= listNode.next;
        }
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(left == 1){
            return reverseN(head,right);
        }
        head.next = reverseBetween(head.next,left-1,right-1);
        return head;
    }

    ListNode successor = null;

    ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        ListNode last = reverseN(head.next, n - 1);

        head.next.next = head;
        head.next = successor;
        return last;
    }

    @Test
    public void testReverseList(){
        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(2);
        listNode1.next.next = new ListNode(3);
        listNode1.next.next.next = new ListNode(4);
        listNode1.next.next.next.next = new ListNode(5);
        listNode1.next.next.next.next.next = new ListNode(6);
        ListNode listNode = reverseList(listNode1);
        while (listNode!=null){
            System.out.println(listNode.val);
            listNode= listNode.next;
        }
    }


    public ListNode reverseList(ListNode head) {
        return reverse(head);
    }

    ListNode reverse(ListNode head){
        if(head == null||head.next == null){
            return head;
        }
        ListNode last = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }


    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA,p2 = headB;
        while(p1!=p2){
            if(p1==null){
                p1 = headB;
            }else{
                p1 = p1.next;
            }
            if(p2==null){
                p2 = headA;
            }else{
                p2 = p2.next;
            }
        }
        return p1;
    }

    @Test
    public void testMiddleNode(){
        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(2);
        listNode1.next.next = new ListNode(3);
        listNode1.next.next.next = new ListNode(4);
        listNode1.next.next.next.next = new ListNode(5);
        listNode1.next.next.next.next.next = new ListNode(6);
        ListNode listNode = middleNode(listNode1);
        while (listNode!=null){
            System.out.println(listNode.val);
            listNode= listNode.next;
        }
    }

    public ListNode middleNode(ListNode head) {
        ListNode slow = head,fast = head;
        while(fast!=null&&fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    @Test
    public void testRemoveNthFromEnd(){
        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(2);
//        listNode1.next.next = new ListNode(3);
//        listNode1.next.next.next = new ListNode(4);
//        listNode1.next.next.next.next = new ListNode(5);
        ListNode listNode = removeNthFromEnd(listNode1,2);
        while (listNode!=null){
            System.out.println(listNode.val);
            listNode= listNode.next;
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode node = findNthFromEnd(dummy,n+1);
        node.next = node.next.next;
        return dummy.next;
    }

    public ListNode findNthFromEnd(ListNode dummy, int n){
        ListNode p1 = dummy;
        for (int i = 0; i < n; i++) {
            p1 = p1.next;
        }
        ListNode p2 = dummy;
        while(p1!=null){
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }

    @Test
    public void testMergeKLists(){
        ListNode listNode1 = new ListNode(1);
        listNode1.next = new ListNode(4);
        listNode1.next.next = new ListNode(5);
        ListNode listNode2 = new ListNode(1);
        listNode2.next = new ListNode(3);
        listNode2.next.next = new ListNode(4);
        ListNode listNode3 = new ListNode(2);
        listNode3.next = new ListNode(6);
        ListNode[] lists = new ListNode[]{listNode1,listNode2,listNode3};
        ListNode listNode = mergeKLists(lists);
        while (listNode!=null){
            System.out.println(listNode.val);
            listNode= listNode.next;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头结点
        ListNode dummy = new ListNode(-1);
        ListNode p = dummy;
        // 优先级队列，最小堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
                lists.length, (a, b)->(a.val - b.val));
        // 将 k 个链表的头结点加入最小堆
        for (ListNode head : lists) {
            if (head != null)
                pq.add(head);
        }

        while (!pq.isEmpty()) {
            // 获取最小节点，接到结果链表中
            ListNode node = pq.poll();
            p.next = node;
            if (node.next != null) {
                pq.add(node.next);
            }
            // p 指针不断前进
            p = p.next;
        }
        return dummy.next;
    }

    @Test
    public void testPartition(){
        ListNode head = new ListNode(1);
        head.next = new ListNode(4);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(2);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(2);
        ListNode listNode = partition(head, 3);
        while (listNode!=null){
            System.out.println(listNode.val);
            listNode= listNode.next;
        }
    }


    public ListNode partition(ListNode head, int x) {
        ListNode dummy1 = new ListNode(-1);
        ListNode dummy2 = new ListNode(-1);
        ListNode p1 = dummy1, p2 = dummy2;

        ListNode p = head;

        while (p != null) {
            if (p.val >= x) {
                p2.next = p;
                p2 = p2.next;
            } else {
                p1.next = p;
                p1 = p1.next;
            }

            ListNode temp = p.next;
            p.next = null;
            p = temp;
        }
        p1.next = dummy2.next;

        return dummy1.next;
    }

    @Test
    public void testMergeTwoLists(){
        ListNode list1 = new ListNode(1);
        list1.next = new ListNode(2);
        list1.next.next = new ListNode(4);
        ListNode list2 = new ListNode(1);
        list2.next = new ListNode(3);
        list2.next.next = new ListNode(4);
        ListNode listNode = mergeTwoLists(list1, list2);
        while (listNode.next!=null){
            System.out.println(listNode.val);
            listNode= listNode.next;
        }
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dump = new ListNode(-1),p = dump;
        ListNode p1 = list1,p2 = list2;
        while (p1 != null && p2 != null) {
            if (p1.val > p2.val) {
                p.next = p2;
                p2 = p2.next;
            } else {
                p.next = p1;
                p1 = p1.next;
            }
            p = p.next;
        }

        if (p1 != null) {
            p.next = p1;
        }

        if (p2 != null) {
            p.next = p2;
        }

        return dump.next;
    }

}
